package Z.dailyExercise._0225;

public class _剑指Offer17打印从1到最大的n位数 {

    /**
     * n位数的最大数 就是10的n次幂-1
     * ==耗时耗力
     * @param n
     * @return
     */
    public int[] printNumbers(int n) {
        int[] res = new int[(int) Math.pow(10,n)-1];
        int num =0;

        while (num != Math.pow(10,n)-1){
            res[num] = num+1;
            num++;

        }

        return res;

    }

    /**
     * 存在大数的情况下：借助迭代进行全排列
     * 从高位往低位开始 迭代用于地位的迭代 for循环用于高位固定
     */

    int n;
    int nine =0;//用于统计当前数字中9de个数 用于去除最开始的多余0
    int start;//标志实际返回数字的开始位
    //StringBuilder res;
    int[] res;
    int count=0;//用于数组计数
    char[] num,loop={'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};

    public int[] printNumbers1(int n) {
        this.n = n;
      //  res = new StringBuilder();
        res= new int[(int)Math.pow(10, n) - 1];
        num = new char[n];
        start = n-1;
        dfs(0);

        //res.deleteCharAt(res.length()-1);
        //return res.toString();
        return res;

    }
    void dfs(int x){
        if (x==n){
            String s = String.valueOf(num).substring(start);//去除前面的0
            if (!s.equals("0")){//出去最开始的全零
                //res.append(s+",");
                res[count++] = Integer.parseInt(s);
            }

            if (n-start== nine){
                //用于判断当前是不是到全9 到了就需要statr-1
                start--;
            }

            return;
        }

        for (char i :loop){
            if (i=='9'){
                nine++;
            }
            num[x] = i;
            dfs(x+1);
        }

        nine--;//从新的一个阶段开始 nine进行回溯-1
    }
}
